package com.leetcode;

import ds.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No94
 * @description 94. 二叉树的中序遍历
 * @date 2021/3/14 下午5:18
 */
public class No94 {
    public static void main(String[] args) {
        /**
         *                1
         *               / \
         *              2   3
         *                 /
         *                5
         */
        TreeNode root = new TreeNode(1);
        TreeNode t1 = new TreeNode(2);
        TreeNode t2 = new TreeNode(3);
        TreeNode t3 = new TreeNode(5);
        root.left = t1;
        root.right = t2;
        t2.left = t3;
        List<Integer> res1 = inorderTraversal(root);
        print(res1);
        List<Integer> res2 = inorderTraversal2(root);
        print(res2);

    }

    // 方法一 递归
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        helper(root,res);
        return res;

    }

    private static void helper(TreeNode root, List<Integer> res) {
        if(root == null){
            return;
        }
        helper(root.left,res);
        res.add(root.val);
        helper(root.right,res);
    }

    public static List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        // 使用Linkedlist模拟栈
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();

        while (!stack.isEmpty() || root != null){
            if(root != null){
                stack.addLast(root);
                root = root.left;
            }else{
                TreeNode t = stack.removeLast();
                res.add(t.val);
                root = t.right;
            }
        }
        return res;
    }

    public static void print(List<Integer> res){
        int size = res.size();
        for (int i = 0; i < size ; i++) {
            System.out.print(res.get(i));
            if(i != size - 1){
                System.out.print("-");
            }

        }
        System.out.println();
    }

}
